package leetcode_core.sort;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

public class InsertSort {
    public static void insertSort(int[] arr){
        //插入排序
        if(arr == null || arr.length <2){
            return;
        }
        for(int i = 1;i<arr.length;i++){
            for(int j = i-1;j>=0&&arr[j]>arr[j+1];j--){
                swap(arr,j,j+1);
            }
        }
    }
    //二分搜索查找
    public static void binaryInsertSort(int[] arr){
        if(arr == null || arr.length <2){
            return;
        }
        //已知0-i-1是有序的
        for(int i = 1;i<arr.length;i++){//对于a[i],在0-i-1的位置上寻找合适的位置
            //首先比较是否能够形成有序的的数组
            if(arr[i]>=arr[i-1]){continue;}
            //否则的话就是不能,需要寻找合适的位置,一个个换位置
            //定义搜索区间[0,i-1]
            int temp = arr[i];
            int left = 0,right = i-1;
            int mostLeft = -1;
            while (left <= right){
                int mid = left+(right-left)/2;
                //找到arr[i]所在的位置
                //如果0-i-1中有和arr[i]这个数相等的,那么就寻找右侧的边界
                //如果没有相等的,那么就寻找一个合适的位置
                //目前来说,已经是arr[i-1]>arr[i]
                //因此想要找到arr[j]<arr[i],这个数并不是一找到就马上返回
                //而是说最后一个这样的数
                if(arr[mid]<arr[i]){//这个数暂时记住它,后面可以用
                    left = mid+1;//然后因为已经检查过了,那么它的左边就没有意义了,因为不是边界,想找的是右侧的边界
                    mostLeft = left;
                }else{//arr[mid]>=arr[i]
                    right = mid-1;
                }
            }
            //然后对这个mostLeft之前的位置向右挪
            for(int j = i;j>mostLeft;j--){
                arr[j] = arr[j-1];
            }
            arr[mostLeft] =temp;
        }
    }

    private static void swap(int[] arr,int i,int j){
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }

    @Test
    public void test(){
        int[] arr = {7, 1, 3, 5, 1, 6, 8, 1, 3, 5, 7, 5, 6};
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
